{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sliding Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: slidingPuzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #滑动谜题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个 <code>2 x 3</code> 的板上（<code>board</code>）有 5 块砖瓦，用数字 <code>1~5</code> 来表示, 以及一块空缺用&nbsp;<code>0</code>&nbsp;来表示。一次 <strong>移动</strong> 定义为选择&nbsp;<code>0</code>&nbsp;与一个相邻的数字（上下左右）进行交换.</p>\n",
    "\n",
    "<p>最终当板&nbsp;<code>board</code>&nbsp;的结果是&nbsp;<code>[[1,2,3],[4,5,0]]</code>&nbsp;谜板被解开。</p>\n",
    "\n",
    "<p>给出一个谜板的初始状态&nbsp;<code>board</code>&nbsp;，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/29/slide1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[1,2,3],[4,0,5]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>交换 0 和 5 ，1 步完成\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/29/slide2-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[1,2,3],[5,4,0]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>没有办法完成谜板\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/29/slide3-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[4,1,2],[5,0,3]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "最少完成谜板的最少移动次数是 5 ，\n",
    "一种移动路径:\n",
    "尚未移动: [[4,1,2],[5,0,3]]\n",
    "移动 1 次: [[4,1,2],[0,5,3]]\n",
    "移动 2 次: [[0,1,2],[4,5,3]]\n",
    "移动 3 次: [[1,0,2],[4,5,3]]\n",
    "移动 4 次: [[1,2,0],[4,5,3]]\n",
    "移动 5 次: [[1,2,3],[4,5,0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>board.length == 2</code></li>\n",
    "\t<li><code>board[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= board[i][j] &lt;= 5</code></li>\n",
    "\t<li><code>board[i][j]</code>&nbsp;中每个值都 <strong>不同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sliding-puzzle](https://leetcode.cn/problems/sliding-puzzle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sliding-puzzle](https://leetcode.cn/problems/sliding-puzzle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,0,5]]', '[[1,2,3],[5,4,0]]', '[[4,1,2],[5,0,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        b = [str(i) for i in sum(board, [])]\n",
    "        start = \"\".join(b)\n",
    "        target = \"123450\"\n",
    "        neighbor = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]\n",
    "        q = deque()\n",
    "        visited = set()\n",
    "        q.append(start)\n",
    "        visited.add(start)\n",
    "        step = 0\n",
    "\n",
    "        while len(q) != 0:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                cur = q.popleft()\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                \n",
    "                start_index = cur.index('0')\n",
    "                for end_index in neighbor[start_index]:\n",
    "                    char = list(cur)\n",
    "                    char[start_index], char[end_index] = char[end_index], char[start_index]\n",
    "                    new_board = \"\".join(char)\n",
    "                    if new_board not in visited:\n",
    "                        q.append(new_board)\n",
    "                        visited.add(new_board)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 除了暴力破解没有其他任何方法\n",
    "        # 最短路径问题\n",
    "        # 广度优先搜索\n",
    "        hashmap = {0:[1,3], 1:[0,2,4], 2:[1,5], 3:[0,4], 4:[1,3,5], 5:[2,4]}\n",
    "        start = ''\n",
    "        for x in range(2):\n",
    "            for y in range(3):\n",
    "                start += str(board[x][y])\n",
    "        queue = deque([start])\n",
    "        visited = {start}\n",
    "        goal = '123450'\n",
    "        if start == goal:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                index = cur.find('0')\n",
    "                for exch in hashmap[index]:\n",
    "                    nex = ''\n",
    "                    for i in range(6):\n",
    "                        if i == index:\n",
    "                            nex += cur[exch]\n",
    "                        elif i == exch:\n",
    "                            nex += cur[index]\n",
    "                        else:\n",
    "                            nex += cur[i]\n",
    "                    if nex == goal:\n",
    "                        return ans\n",
    "                    if nex not in visited:\n",
    "                        visited.add(nex)\n",
    "                        queue.append(nex)\n",
    "            ans += 1    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board):\n",
    "        final = [[1, 2, 3], [4, 5, 0]]\n",
    "        exist = []\n",
    "        exist.append(board)\n",
    "        wait = []\n",
    "        step = 0\n",
    "        wait.append([board, step])\n",
    "        if board == final:\n",
    "            return 0\n",
    "        while wait != []:\n",
    "            [board, step] = wait.pop(0)\n",
    "            for i in range(2):\n",
    "                if 0 in board[i]:\n",
    "                    row = i\n",
    "                    col = board[i].index(0)\n",
    "                    break\n",
    "\n",
    "            cur = copy.deepcopy(board)\n",
    "            if row == 0:\n",
    "                cur[row][col] = cur[row + 1][col]\n",
    "                cur[row + 1][col] = 0\n",
    "                if cur == final:\n",
    "                    return step + 1\n",
    "                if cur not in exist:\n",
    "                    exist.append(cur)\n",
    "                    wait.append([cur, step + 1])\n",
    "            elif row == 1:\n",
    "                cur[row][col] = cur[row - 1][col]\n",
    "                cur[row - 1][col] = 0\n",
    "                if cur == final:\n",
    "                    return step + 1\n",
    "                if cur not in exist:\n",
    "                    exist.append(cur)\n",
    "                    wait.append([cur, step + 1])\n",
    "\n",
    "            cur = copy.deepcopy(board)\n",
    "            if col == 1 or col == 0:\n",
    "                cur[row][col] = cur[row][col + 1]\n",
    "                cur[row][col + 1] = 0\n",
    "                if cur == final:\n",
    "                    return step + 1\n",
    "                if cur not in exist:\n",
    "                    exist.append(cur)\n",
    "                    wait.append([cur, step + 1])\n",
    "\n",
    "            cur = copy.deepcopy(board)\n",
    "            if col == 1 or col == 2:\n",
    "                cur[row][col] = cur[row][col - 1]\n",
    "                cur[row][col - 1] = 0\n",
    "                if cur == final:\n",
    "                    return step + 1\n",
    "                if cur not in exist:\n",
    "                    exist.append(cur)\n",
    "                    wait.append([cur, step + 1])\t\t\t\t\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    DIR, ROW, COL = [[1, -1, 0, 0], [0, 0, 1, -1]], 2, 3\n",
    "\n",
    "    def __hashVal(self, board):\n",
    "        return ((board[0][0] << 15) | (board[0][1] << 12) | (board[0][2] << 9)\n",
    "        | (board[1][0] << 6) | (board[1][1] << 3) | board[1][2])\n",
    "\n",
    "    def __getNext(self, board):\n",
    "        r0, c0 = self.__zeroPos(board)\n",
    "        ans = []\n",
    "        for i in range(4):\n",
    "            r, c = r0 + Solution.DIR[0][i], c0 + Solution.DIR[1][i]\n",
    "            if r >= 0 and c >= 0 and r < Solution.ROW and c < Solution.COL:\n",
    "                board[r0][c0], board[r][c] = board[r][c], board[r0][c0]\n",
    "                ans.append(self.__hashVal(board))\n",
    "                board[r0][c0], board[r][c] = board[r][c], board[r0][c0]\n",
    "        return ans\n",
    "\n",
    "    def __zeroPos(self, board):\n",
    "        for i in range(Solution.ROW):\n",
    "            for j in range(Solution.COL):\n",
    "                if board[i][j] == 0:\n",
    "                    return i, j\n",
    "        return -1, -1\n",
    "\n",
    "    def __deHash(self, board, val):\n",
    "        board[0][0] = val >> 15\n",
    "        board[0][1] = (val >> 12) & 0b111\n",
    "        board[0][2] = (val >> 9) & 0b111\n",
    "        board[1][0] = (val >> 6) & 0b111\n",
    "        board[1][1] = (val >> 3) & 0b111\n",
    "        board[1][2] = val & 0b111\n",
    "\n",
    "    def slidingPuzzle(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        init, target = self.__hashVal(board), 42792\n",
    "        if init == target:\n",
    "            return 0\n",
    "        dic, que = {init:0}, Queue()\n",
    "        que.put(init)\n",
    "        while not que.empty():\n",
    "            cur = que.get()\n",
    "            self.__deHash(board, cur)\n",
    "            for i in self.__getNext(board):\n",
    "                if i == target:\n",
    "                    return dic[cur] + 1\n",
    "                if i not in dic:\n",
    "                    dic[i] = dic[cur] + 1\n",
    "                    que.put(i)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        def cal_state(board):\n",
    "            return ''.join([''.join(map(str, row)) for row in board])\n",
    "\n",
    "        row, col = 0, 0\n",
    "        for r in range(2):\n",
    "            for c in range(3):\n",
    "                if board[r][c] == 0:\n",
    "                    row, col = r, c\n",
    "                    break\n",
    "\n",
    "        q = collections.deque([(0, cal_state(board), board, row, col)])\n",
    "        target = cal_state([[1, 2, 3], [4, 5, 0]])\n",
    "        vis = {cal_state(board)}\n",
    "        while q:\n",
    "            step, state, board, r, c = q.popleft()\n",
    "            if state == target:\n",
    "                return step\n",
    "            for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:\n",
    "                if 0 <= nr < 2 and 0 <= nc < 3:\n",
    "                    nboard = [[x for x in row] for row in board]\n",
    "                    nboard[nr][nc], nboard[r][c] = nboard[r][c], nboard[nr][nc]\n",
    "                    nstate = cal_state(nboard)\n",
    "                    if nstate not in vis:\n",
    "                        vis.add(nstate)\n",
    "                        q.append((step + 1, nstate, nboard, nr, nc))\n",
    "\n",
    "        return -1\n",
    "                    \n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        def cal_state(board):\n",
    "            return ''.join([''.join(map(str, row)) for row in board])\n",
    "\n",
    "        def nstates(board, r, c):\n",
    "            ans = []\n",
    "            for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:\n",
    "                if 0 <= nr < 2 and 0 <= nc < 3:\n",
    "                    nboard = [[x for x in row] for row in board]\n",
    "                    nboard[nr][nc], nboard[r][c] = nboard[r][c], nboard[nr][nc]\n",
    "                    nstate = cal_state(nboard)\n",
    "                    ans.append((nstate, nboard, nr, nc))\n",
    "            return ans\n",
    "\n",
    "        row, col = 0, 0\n",
    "        for r in range(2):\n",
    "            for c in range(3):\n",
    "                if board[r][c] == 0:\n",
    "                    row, col = r, c\n",
    "                    break\n",
    "\n",
    "        target_board = [[1, 2, 3], [4, 5, 0]]\n",
    "        state = cal_state(board)\n",
    "        target = cal_state(target_board)\n",
    "        q = collections.deque([(0, state, board, row, col)])\n",
    "        revq = collections.deque([(0, target, target_board, 1, 2)])\n",
    "        steps = {state: 0}\n",
    "        revsteps = {target: 0}\n",
    "\n",
    "        while q or revq:\n",
    "            if q:\n",
    "                step, state, board, r, c = q.popleft()\n",
    "                if state in revsteps:\n",
    "                    return step + revsteps[state]\n",
    "                else:\n",
    "                    for nstate, nboard, nr, nc in nstates(board, r, c):\n",
    "                        if nstate not in steps:\n",
    "                            steps[nstate] = step + 1\n",
    "                            q.append((step + 1, nstate, nboard, nr, nc))\n",
    "            if revq:\n",
    "                step, state, board, r, c = revq.popleft()\n",
    "                if state in steps:\n",
    "                    return step + steps[state]\n",
    "                else:\n",
    "                    for nstate, nboard, nr, nc in nstates(board, r, c):\n",
    "                        if nstate not in revsteps:\n",
    "                            revsteps[nstate] = step + 1\n",
    "                            revq.append((step + 1, nstate, nboard, nr, nc))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        def num2board(n):\n",
    "            board = [[0 for j in range(3)] for i in range(2)]\n",
    "            k = 100000\n",
    "            for i in range(2):\n",
    "                for j in range(3):\n",
    "                    board[i][j] = n // k % 10\n",
    "                    k //= 10\n",
    "            return board\n",
    "\n",
    "        def board2num(board):\n",
    "            n = 0\n",
    "            for i in range(2):\n",
    "                for j in range(3):\n",
    "                    n = n * 10 + board[i][j]\n",
    "            return n\n",
    "\n",
    "        q = deque([board2num(board) * 1000])\n",
    "        v = set()\n",
    "        d = [[0, -1], [-1, 0], [0, 1], [1, 0]]\n",
    "        while q:\n",
    "            s = q[0]\n",
    "            q.popleft()\n",
    "            n = s // 1000\n",
    "            step = s % 1000\n",
    "            if n == 123450: return step\n",
    "            g = num2board(n)\n",
    "            for i in range(2):\n",
    "                for j in range(3):\n",
    "                    if g[i][j] == 0: break\n",
    "                if j < 3 and g[i][j] == 0: break\n",
    "\n",
    "            for rc in d:\n",
    "                r, c = i + rc[0], j + rc[1]\n",
    "                if 0 <= r < 2 and 0 <= c < 3:\n",
    "                    g[i][j], g[r][c] = g[r][c], g[i][j]\n",
    "                    n = board2num(g)\n",
    "                    if n not in v:\n",
    "                        v.add(n)\n",
    "                        q.append(n * 1000 + step + 1)\n",
    "                    g[i][j], g[r][c] = g[r][c], g[i][j]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        m = 2\n",
    "        n = 3\n",
    "\n",
    "        target = '123450'\n",
    "        cur = ''.join([str(cell) for row in board for cell in row])\n",
    "        steps = 0\n",
    "        visited = set()\n",
    "\n",
    "        queue = [cur]\n",
    "\n",
    "        # [[3,2,4],[1,5,0]]\n",
    "\n",
    "        def exchange(state, i, j):\n",
    "            if j < 0 or j >= m * n:\n",
    "                return False\n",
    "            state[i] = state[j]\n",
    "            state[j] = '0'\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if cur == target:\n",
    "                    return steps\n",
    "                if cur in visited:\n",
    "                    continue\n",
    "                visited.add(cur)\n",
    "                for i in range(len(cur)):\n",
    "                    if cur[i] == '0':\n",
    "                        if i % n == 0:\n",
    "                            for j in [1, -3, 3]:\n",
    "                                s = list(cur)\n",
    "                                if exchange(s, i, i + j) != False:\n",
    "                                    queue.append(''.join(s))\n",
    "                        elif i % n == n - 1:\n",
    "                            for j in [-1, -3, 3]:\n",
    "                                s = list(cur)\n",
    "                                if exchange(s, i, i + j) != False:\n",
    "                                    queue.append(''.join(s))\n",
    "                        else:\n",
    "                            for j in [1, -1, -3, 3]:\n",
    "                                s = list(cur)\n",
    "                                if exchange(s, i, i + j) != False:\n",
    "                                    queue.append(''.join(s))\n",
    "            steps += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        s = ''.join(str(c) for row in board for c in row)\n",
    "        move = {\n",
    "            0: [1, 3],\n",
    "            1: [0, 2, 4],\n",
    "            2: [1, 5],\n",
    "            3: [0, 4],\n",
    "            4: [1, 3, 5],\n",
    "            5: [2, 4]\n",
    "        }\n",
    "\n",
    "        q, visited, ans = [s], set(), 0\n",
    "\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for s in q:\n",
    "                if s == '123450':\n",
    "                    return ans\n",
    "                arr, idx = [c for c in s], s.index('0')\n",
    "                for nxt in move[idx]:\n",
    "                    new_arr = arr[::]\n",
    "                    new_arr[idx], new_arr[nxt] = new_arr[nxt], new_arr[idx]\n",
    "                    new_s = ''.join(new_arr)\n",
    "                    if new_s not in visited:\n",
    "                        tmp.append(new_s)\n",
    "                        visited.add(new_s)\n",
    "            q = tmp\n",
    "            ans += 1\n",
    "        return -1\n",
    "                    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def slidingPuzzle(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        er_one = [None] * (row * col)\n",
    "        # 二维转换一维\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                er_one[i * col + j] = board[i][j]\n",
    "        # 最后跳出循环的条件\n",
    "        c_loc = [0]*(row*col)\n",
    "        for i in range(1,row*col):\n",
    "            c_loc[i-1] = i\n",
    "        # 步数\n",
    "        step = 0\n",
    "        # 方向\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        # 当前情况\n",
    "        cur = [er_one]\n",
    "        # 已访问的情况\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            next_time = []\n",
    "            for tmp in cur:\n",
    "                # 当此时的情况和正确的情况一样是,返回步数\n",
    "                if tmp == c_loc:\n",
    "                    return step\n",
    "                # 没有访问过的情况\n",
    "                if tuple(tmp) not in visited:\n",
    "                    # 添加到已访问\n",
    "                    visited.add(tuple(tmp))\n",
    "                    # 找到一维数组的0的位置\n",
    "                    zero_loc = tmp.index(0)\n",
    "                    # 找到对应二维数组的行和列\n",
    "                    x, y = divmod(zero_loc, col)\n",
    "                    # 进行上下左右交换\n",
    "                    for p,q in dirs:\n",
    "                        tmp_x = x + p\n",
    "                        tmp_y = y + q\n",
    "                        if  0<=tmp_x < row and 0<=tmp_y<col:\n",
    "                            # 要拷贝一份\n",
    "                            tmp_tmp = tmp[:]\n",
    "                            tmp_tmp[tmp_x*col+tmp_y],tmp_tmp[zero_loc] = tmp_tmp[zero_loc],tmp_tmp[tmp_x*col+tmp_y]\n",
    "                            next_time.append(tmp_tmp)\n",
    "            step += 1\n",
    "            cur = next_time\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        board = board[0]+board[1]  # 把board连起来变一维\n",
    "        moves = [(1, 3), (0, 2, 4), (1, 5), (0, 4), (1, 3, 5), (2, 4)]  # 每个位置的0可以交换的位置\n",
    "        q, visited = [(tuple(board), board.index(0), 0)], set()  # bfs队列和已访问状态记录\n",
    "        while q:\n",
    "            state, now, step = q.pop(0)  # 分别代表当前状态，0的当前位置和当前步数\n",
    "            if state == (1, 2, 3, 4, 5, 0):  # 找到了\n",
    "                return step\n",
    "            for next in moves[now]:  # 遍历所有可交换位置\n",
    "                _state = list(state)\n",
    "                _state[next], _state[now] = _state[now], state[next]  # 交换位置\n",
    "                _state = tuple(_state)\n",
    "                if _state not in visited:  # 确认未访问\n",
    "                    q.append((_state, next, step+1))\n",
    "            visited.add(state)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def swap(self, s, i, j):\n",
    "        l = list(s)\n",
    "        l[i], l[j] = l[j], l[i]\n",
    "        return \"\".join(l)\n",
    "\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        target = \"123450\"\n",
    "        start = \"\"\n",
    "        for i in range(2):\n",
    "            for j in range(3):\n",
    "                start += str(board[i][j])\n",
    "        d = [[1, 3],[0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]\n",
    "        q = deque()\n",
    "        q.append(start)\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        step = 0\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                t = q.popleft()\n",
    "                if t == target:\n",
    "                    return step\n",
    "                for j in range(6):\n",
    "                    if t[j] == '0':\n",
    "                        break\n",
    "                for item in d[j]:\n",
    "                    temp = self.swap(t, item, j)\n",
    "                    if temp not in visited:\n",
    "                        visited.add(temp)\n",
    "                        q.append(temp)\n",
    "                \n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        visited = [board[0]+board[1]]\n",
    "        board = visited[0]\n",
    "        q = [board]\n",
    "        target  = [1,2,3,4,5,0]\n",
    "        help = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]]\n",
    "        count = 0\n",
    "        if board==target:\n",
    "            return count\n",
    "        while q:\n",
    "            length = len(q)\n",
    "            count += 1\n",
    "            for i in range(length):\n",
    "                now_board = q.pop()\n",
    "                index = now_board.index(0)\n",
    "                for i in help[index]:\n",
    "                    new_board = now_board.copy()\n",
    "                    new_board[index] = now_board[i]\n",
    "                    new_board[i] = 0\n",
    "                    if new_board==target:\n",
    "                        return count\n",
    "                    elif new_board not in visited:\n",
    "                        q.insert(0,new_board)\n",
    "                        visited.append(new_board)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        visited = [board[0]+board[1]]\n",
    "        board = visited[0]\n",
    "        q = [board]\n",
    "        target  = [1,2,3,4,5,0]\n",
    "        help = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]]\n",
    "        count = 0\n",
    "        if board==target:\n",
    "            return count\n",
    "        while q:\n",
    "            length = len(q)\n",
    "            count += 1\n",
    "            for i in range(length):\n",
    "                now_board = q.pop()\n",
    "                index = now_board.index(0)\n",
    "                for i in help[index]:\n",
    "                    new_board = now_board.copy()\n",
    "                    new_board[index] = now_board[i]\n",
    "                    new_board[i] = 0\n",
    "                    if new_board==target:\n",
    "                        return count\n",
    "                    elif new_board not in visited:\n",
    "                        q.insert(0,new_board)\n",
    "                        visited.append(new_board)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        used = set()\n",
    "        cnt = 0\n",
    "\n",
    "        moves = {\n",
    "            0: [1, 3],\n",
    "            1: [0, 2, 4],\n",
    "            2: [1, 5],\n",
    "            3: [0, 4],\n",
    "            4: [1, 3, 5],\n",
    "            5: [2, 4]\n",
    "        }\n",
    "\n",
    "        s = ''.join(str(ch) for row in board for ch in row)\n",
    "        q = [s]\n",
    "\n",
    "        while q:\n",
    "            new = []\n",
    "            for word in q:                              \n",
    "                if word == '123450':\n",
    "                    return cnt\n",
    "                used.add(word)\n",
    "\n",
    "                zero_index = word.index('0')\n",
    "                arr = [ch for ch in word]\n",
    "                for i in moves[zero_index]:\n",
    "                    new_arr = arr[:]\n",
    "                    new_arr[zero_index], new_arr[i] = new_arr[i], new_arr[zero_index]\n",
    "                    new_s = ''.join(new_arr)\n",
    "\n",
    "                    if new_s not in used:\n",
    "                        used.add(new_s)\n",
    "                        new.append(new_s)\n",
    "\n",
    "            cnt += 1\n",
    "            q = new\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "import queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    RECORDS = []\n",
    "    MIN_STEP = None\n",
    "    TRAVELED = set()\n",
    "\n",
    "    def slidingPuzzle(self, board: list) -> int:\n",
    "        return self._sliding_puzzle2(board)\n",
    "\n",
    "    def _sliding_puzzle(self, board: list, step: int, path: list,\n",
    "                        initial_snap_shot):\n",
    "        is_ok, snapshot, zero = self._is_ok(board)\n",
    "        if is_ok:\n",
    "            self.RECORDS.append(copy.deepcopy(path))\n",
    "            if (self.MIN_STEP is None) or self.MIN_STEP > step:\n",
    "                self.MIN_STEP = step\n",
    "                return\n",
    "\n",
    "        self.TRAVELED.add(snapshot)\n",
    "        for (x, y) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "            i = zero[0] + x\n",
    "            j = zero[1] + y\n",
    "\n",
    "            if i < 0 or i >= len(board):\n",
    "                continue\n",
    "\n",
    "            if j < 0 or j >= len(board[i]):\n",
    "                continue\n",
    "\n",
    "            tmp = board[i][j]\n",
    "            board[i][j] = 0\n",
    "            board[zero[0]][zero[1]] = tmp\n",
    "            new_snap_shot = self._get_snapshot(board)\n",
    "            if new_snap_shot in self.TRAVELED:\n",
    "                board[zero[0]][zero[1]] = 0\n",
    "                board[i][j] = tmp\n",
    "                continue\n",
    "\n",
    "            path.append(copy.deepcopy(board))\n",
    "            self._sliding_puzzle(board, step + 1, path, initial_snap_shot)\n",
    "            path.pop(-1)\n",
    "            board[zero[0]][zero[1]] = 0\n",
    "            board[i][j] = tmp\n",
    "\n",
    "        return\n",
    "\n",
    "    def _is_ok(self, board):\n",
    "        tmp = []\n",
    "        zero = (-1, -1)\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[i])):\n",
    "                tmp.append(board[i][j])\n",
    "                if board[i][j] == 0:\n",
    "                    zero = (i, j)\n",
    "\n",
    "        return tmp == [1, 2, 3, 4, 5, 0], tuple(tmp), zero\n",
    "\n",
    "    def _get_snapshot(self, board):\n",
    "        _, snapshot, _ = self._is_ok(board)\n",
    "        return snapshot\n",
    "\n",
    "    def _sliding_puzzle2(self, board: list):\n",
    "        q = queue.Queue()\n",
    "        q.put(board)\n",
    "        size = 1\n",
    "        step = 0\n",
    "        traveled = set()\n",
    "        while not q.empty():\n",
    "            tmp_size = 0\n",
    "            for k in range(size):\n",
    "                brd = q.get()\n",
    "                is_ok, snapshot, zero = self._is_ok(brd)\n",
    "                if is_ok:\n",
    "                    return step\n",
    "\n",
    "                traveled.add(snapshot)\n",
    "                for (x, y) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                    i = zero[0] + x\n",
    "                    j = zero[1] + y\n",
    "\n",
    "                    if i < 0 or i >= len(brd):\n",
    "                        continue\n",
    "\n",
    "                    if j < 0 or j >= len(brd[i]):\n",
    "                        continue\n",
    "\n",
    "                    tmp = brd[i][j]\n",
    "                    brd[i][j] = 0\n",
    "                    brd[zero[0]][zero[1]] = tmp\n",
    "                    new_snapshot = self._get_snapshot(brd)\n",
    "                    if new_snapshot in traveled:\n",
    "                        brd[zero[0]][zero[1]] = 0\n",
    "                        brd[i][j] = tmp\n",
    "                        continue\n",
    "\n",
    "                    q.put(copy.deepcopy(brd))\n",
    "                    brd[zero[0]][zero[1]] = 0\n",
    "                    brd[i][j] = tmp\n",
    "                    tmp_size += 1\n",
    "\n",
    "            size = tmp_size\n",
    "            step += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        stack = []\n",
    "        \n",
    "        def dfs(pos: int, step: int):\n",
    "            x = 0\n",
    "            for i in range (6):\n",
    "                x += line[5-i]*10**i\n",
    "            stack.append(x)\n",
    "            if x in memo and memo[x] <= step:\n",
    "                return\n",
    "            memo[x] = step\n",
    "            if x == goal:\n",
    "                return\n",
    "            \n",
    "            for i in range (4):\n",
    "                if (abs(move[i])>1 and pos+move[i]>=0 and pos+move[i]<=5) or (move[i]==-1 and pos!=0 and pos!=3) or (move[i]==1 and pos !=2 and pos!=5):\n",
    "                    temp = line[pos+move[i]]\n",
    "                    line[pos+move[i]] = line[pos]\n",
    "                    line[pos] = temp\n",
    "                    dfs(pos+move[i], step+1)\n",
    "                    stack.pop()\n",
    "                    temp = line[pos+move[i]]\n",
    "                    line[pos+move[i]] = line[pos]\n",
    "                    line[pos] = temp\n",
    "                    \n",
    "        goal = 123450\n",
    "        memo = {}\n",
    "        move = [-3,3,-1,1]\n",
    "        line = [0 for _ in range(6)]\n",
    "        line[0:3], line[3:6] = board[0][0:3], board[1][0:3]\n",
    "        dfs(line.index(0), 0)\n",
    "\n",
    "        if goal in memo:\n",
    "            return memo[goal]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        # 012\n",
    "        # 345\n",
    "        neighbors = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]]\n",
    "        start = board[0]+board[1]\n",
    "        target = [1,2,3,4,5,0]\n",
    "        queue = collections.deque([start])\n",
    "        visit = set()\n",
    "        visit.add(tuple(start))\n",
    "        res = 0\n",
    "        while(queue):\n",
    "            l = len(queue)\n",
    "            for _ in range(l):\n",
    "                cur = queue.popleft()\n",
    "                if cur == target:\n",
    "                    return res\n",
    "                pos = cur.index(0)\n",
    "                for neighbor in neighbors[pos]:\n",
    "                    tmp = cur[:]\n",
    "                    tmp[neighbor], tmp[pos] = tmp[pos], tmp[neighbor]\n",
    "                    if tuple(tmp) not in visit:\n",
    "                        queue.append(tmp)\n",
    "                        visit.add(tuple(tmp))\n",
    "            res += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        base = pos = end = 0\n",
    "        direction = [1, 3, -1, -3]\n",
    "        for i, (n, m) in enumerate(zip(board[0] + board[1], (1, 2, 3, 4, 5, 0))):\n",
    "            pos = i if not n else pos\n",
    "            base |= n << (i * 3)\n",
    "            end |= m << (i * 3)\n",
    "\n",
    "        queue, used, step = deque([(base, pos)]), set(), 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                sta, pos = queue.popleft()\n",
    "                if sta == end:\n",
    "                    return step\n",
    "                if sta not in used:\n",
    "                    used.add(sta)\n",
    "                    for d in direction:\n",
    "                        if 0 <= (p:= pos + d) <= 5 and p & pos != 2:\n",
    "                            queue.append((sta & ~(7 << (p * 3)) | ((sta >> (p * 3) & 7) << (pos * 3)), p))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        self.initial = self.board_to_string(board)\n",
    "        self.target = \"123450\"\n",
    "        self.visited = {}\n",
    "        if self.initial == self.target:\n",
    "            # print(0)\n",
    "            return 0\n",
    "        else:\n",
    "            output = self.bfs()\n",
    "            return output\n",
    "            # print(output)\n",
    "\n",
    "    def board_to_string(self, board):\n",
    "        return ''.join([str(i) for lt in board for i in lt])\n",
    "\n",
    "    def string_to_board(self, string):\n",
    "        board = [[0] * 3 for _ in range(2)]\n",
    "        for i in range(6):\n",
    "            x, y = i // 3, i % 3\n",
    "            board[x][y] = string[i]\n",
    "        return board\n",
    "\n",
    "    def is_in_area(self, x, y):\n",
    "        return 0 <= x < 2 and 0 <= y < 3\n",
    "\n",
    "    def get_nexts(self, string, index):\n",
    "        next_s = []\n",
    "        board = self.string_to_board(string)\n",
    "        x1, y1 = index // 3, index % 3\n",
    "        for x2, y2 in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "            next_x, next_y = x1 + x2, y1 + y2\n",
    "            if self.is_in_area(next_x, next_y):\n",
    "                tmp = copy.deepcopy(board)  # 深拷贝\n",
    "                tmp[x1][y1], tmp[next_x][next_y] = tmp[next_x][next_y], tmp[x1][y1]\n",
    "                s1 = self.board_to_string(tmp)\n",
    "                next_s.append(s1)\n",
    "        return next_s\n",
    "\n",
    "    def bfs(self):\n",
    "        queue = [self.initial]\n",
    "        self.visited[self.initial] = 0\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            index = self.index_0(cur)\n",
    "            next_s = self.get_nexts(cur, index)\n",
    "            for next in next_s:\n",
    "                if next not in self.visited.keys():\n",
    "                    queue.append(next)\n",
    "                    self.visited[next] = self.visited[cur] + 1\n",
    "                    if next == self.target:\n",
    "                        return self.visited[next]\n",
    "        return -1\n",
    "\n",
    "    def index_0(self, string):\n",
    "        for index, i in enumerate(string):\n",
    "            if i == '0':\n",
    "                return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        self.initial = self.board_to_string(board)\n",
    "        self.target = \"123450\"\n",
    "        self.visited = {}\n",
    "        if self.initial == self.target:\n",
    "            # print(0)\n",
    "            return 0\n",
    "        else:\n",
    "            output = self.bfs()\n",
    "            return output\n",
    "            # print(output)\n",
    "\n",
    "    def board_to_string(self, board):\n",
    "        return ''.join([str(i) for lt in board for i in lt])\n",
    "\n",
    "    def string_to_board(self, string):\n",
    "        board = [[0] * 3 for _ in range(2)]\n",
    "        for i in range(6):\n",
    "            x, y = i // 3, i % 3\n",
    "            board[x][y] = string[i]\n",
    "        return board\n",
    "\n",
    "    def is_in_area(self, x, y):\n",
    "        return 0 <= x < 2 and 0 <= y < 3\n",
    "\n",
    "    def get_nexts(self, string, index):\n",
    "        next_s = []\n",
    "        board = self.string_to_board(string)\n",
    "        x1, y1 = index // 3, index % 3\n",
    "        for x2, y2 in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "            next_x, next_y = x1 + x2, y1 + y2\n",
    "            if self.is_in_area(next_x, next_y):\n",
    "                # import copy\n",
    "                # tmp = copy.deepcopy(board)  # 深拷贝\n",
    "                board[x1][y1], board[next_x][next_y] = board[next_x][next_y], board[x1][y1]\n",
    "                next_s.append(self.board_to_string(board))\n",
    "                board[x1][y1], board[next_x][next_y] = board[next_x][next_y], board[x1][y1]\n",
    "        return next_s\n",
    "\n",
    "    def bfs(self):\n",
    "        queue = [self.initial]\n",
    "        self.visited[self.initial] = 0\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            index = self.index_0(cur)\n",
    "            next_s = self.get_nexts(cur, index)\n",
    "            for next in next_s:\n",
    "                if next not in self.visited.keys():\n",
    "                    queue.append(next)\n",
    "                    self.visited[next] = self.visited[cur] + 1\n",
    "                    if next == self.target:\n",
    "                        return self.visited[next]\n",
    "        return -1\n",
    "\n",
    "    def index_0(self, string):\n",
    "        for index, i in enumerate(string):\n",
    "            if i == '0':\n",
    "                return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "\n",
    "        k = 0\n",
    "        board_set = set()\n",
    "        start_x = start_y = -1\n",
    "        array = [['']*3 for _ in range(2)]\n",
    "\n",
    "        for i in range(2):\n",
    "            for j in range(3):\n",
    "                array[i][j] = str(board[i][j])\n",
    "                if board[i][j] == 0:\n",
    "                    start_x ,start_y = i,j\n",
    "\n",
    "        def getString()->str:\n",
    "            return ''.join(array[0])+''.join(array[1])\n",
    "\n",
    "        first_str = getString()\n",
    "\n",
    "        if first_str == '123450':\n",
    "            return 0\n",
    "\n",
    "        board_set.add(first_str)\n",
    "        next_list = []\n",
    "        cur_list = [first_str]\n",
    "\n",
    "        isReach = False\n",
    "\n",
    "        def addString(string):\n",
    "            nonlocal isReach\n",
    "            if string not in board_set:\n",
    "                if string == '123450':\n",
    "                    isReach = True\n",
    "                    return\n",
    "                board_set.add(string)\n",
    "                next_list.append(string)\n",
    "\n",
    "        def bfs(string):\n",
    "            if string[0] == '0':\n",
    "                new_str = string[1] + '0' + string[2:]\n",
    "                addString(new_str)\n",
    "                new_str = string[3] + string[1:3] + '0' + string[4:]\n",
    "                addString(new_str)\n",
    "            elif string[1] == '0':\n",
    "                new_str = '0' + string[0] + string[2:]\n",
    "                addString(new_str)\n",
    "                new_str = string[0] + string[2] + '0' + string[3:]\n",
    "                addString(new_str)\n",
    "                new_str = string[0] + string[4] + string[2] + string[3] + '0' + string[5]\n",
    "                addString(new_str)\n",
    "            elif string[2] == '0':\n",
    "                new_str = string[0] + '0' + string[1] + string[3:]\n",
    "                addString(new_str)\n",
    "                new_str = string[0:2] + string[5] + string[3:5] + '0'\n",
    "                addString(new_str)\n",
    "            elif string[3] == '0':\n",
    "                new_str = '0' + string[1:3] + string[0] + string[4:]\n",
    "                addString(new_str)\n",
    "                new_str = string[0:3] + string[4] + '0' + string[5]\n",
    "                addString(new_str)\n",
    "            elif string[4] == '0':\n",
    "                new_str = string[0]+'0'+string[2]+string[3]+string[1] + string[5]\n",
    "                addString(new_str)\n",
    "                new_str = string[0:3]+'0' + string[3] + string[5]\n",
    "                addString(new_str)\n",
    "                new_str = string[0:4]+string[5] + '0'\n",
    "                addString(new_str)\n",
    "            elif string[5] == '0':\n",
    "                 new_str = string[0:2]+'0' + string[3:5]+string[2]\n",
    "                 addString(new_str)\n",
    "                 new_str = string[0:4] + '0'+ string[4]\n",
    "                 addString(new_str)\n",
    "        \n",
    "        while cur_list:\n",
    "            k+=1\n",
    "            for string in cur_list:\n",
    "                bfs(string)\n",
    "                if isReach:\n",
    "                    return k\n",
    "            cur_list.clear()\n",
    "            cur_list,next_list = next_list,cur_list\n",
    "                \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        ans = [[1,2,3], [4,5,0]]\n",
    "        if ans == board:\n",
    "            return 0\n",
    "        def get_start(board):\n",
    "            for i in range(len(board)):\n",
    "                for j in range(len(board[i])):\n",
    "                    if board[i][j] == 0:\n",
    "                        return (i, j)\n",
    "        x, y = get_start(board)\n",
    "\n",
    "        def bfs(x, y, c, b):\n",
    "            dx = [-1, 1, 0, 0]\n",
    "            dy = [ 0, 0,-1, 1]\n",
    "            q = Queue()\n",
    "            q.put((x, y, c, b))\n",
    "            s = set()\n",
    "            ooo = lambda x, y : x < 0 or y < 0 or x >= len(b) or y >= len(b[0])\n",
    "            while not q.empty():\n",
    "                x, y, c, b = q.get()\n",
    "                for i in range(4):\n",
    "                    nx = x + dx[i]\n",
    "                    ny = y + dy[i]\n",
    "                    if not ooo(nx, ny):\n",
    "                        bak = deepcopy(b)\n",
    "                        bak[nx][ny], bak[x][y] = b[x][y], b[nx][ny]\n",
    "                        if bak == ans:\n",
    "                            return c+1\n",
    "                        t = tuple(map(tuple, bak))\n",
    "                        if t not in s:\n",
    "                            s.add(t)\n",
    "                            q.put((nx, ny, c+1, bak[:]))\n",
    "            return -1\n",
    "        return bfs(x, y, 0, board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        def bfs(q, d1, d2):\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                cur, step = json.loads(cur[0]), cur[1]\n",
    "                for i in range(2):\n",
    "                    for j in range(3):\n",
    "                        if cur[i][j] == 0:\n",
    "                            curi, curj = i, j\n",
    "                            break\n",
    "                for di, dj in (0, 1), (0, -1), (1, 0), (-1, 0):\n",
    "                    if 0 <= curi + di <= 1 and 0 <= curj + dj <= 2:\n",
    "                        nxt = deepcopy(cur)\n",
    "                        nxt[curi][curj], nxt[curi + di][curj + dj] = nxt[curi + di][curj + dj], nxt[curi][curj]\n",
    "                        if json.dumps(nxt) not in d1:\n",
    "                            d1[json.dumps(nxt)] = step + 1\n",
    "                            q.append((json.dumps(nxt), step+1))\n",
    "                        if json.dumps(nxt) in d2:\n",
    "                            return d2[json.dumps(nxt)] + step + 1\n",
    "\n",
    "        target = [[1, 2, 3], [4, 5, 0]]\n",
    "        if board == target:\n",
    "            return 0\n",
    "        q1 = deque([(json.dumps(board), 0)])\n",
    "        q2 = deque([(json.dumps(target), 0)])\n",
    "        state1 = {json.dumps(board): 1}\n",
    "        state2 = {json.dumps(target): 0}\n",
    "        while q1 and q2:\n",
    "            if len(q1) <= len(q2):\n",
    "                ret = bfs(q1, state1, state2)\n",
    "            else:\n",
    "                ret = bfs(q2, state2, state1)\n",
    "            if ret:\n",
    "                return ret\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        for i in range(2):\n",
    "            for j in range(3):\n",
    "                if board[i][j] == 0:\n",
    "                    zero = (i, j)\n",
    "        \n",
    "        res = 20\n",
    "        end = [[1, 2, 3], [4, 5, 0]]\n",
    "        def dfs(i, j, x, y, step, res):\n",
    "            if step > res or not (0 <= i+x <= 1 and 0 <= j+y <= 2):\n",
    "                return res\n",
    "\n",
    "            board[i][j], board[i+x][j+y] = board[i+x][j+y], board[i][j]\n",
    "\n",
    "            if board == end:\n",
    "                board[i][j], board[i+x][j+y] = board[i+x][j+y], board[i][j]\n",
    "                return min(res, step)\n",
    "\n",
    "            for x1, y1 in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                if x + x1 or y + y1:\n",
    "                    res = min(res, dfs(i+x, j+y, x1, y1, step+1, res))\n",
    "\n",
    "            board[i][j], board[i+x][j+y] = board[i+x][j+y], board[i][j]\n",
    "            return res\n",
    "        \n",
    "        res = dfs(*zero, 0, 0, 0, res)\n",
    "        return res if res < 20 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        self.target= \"123450\"\n",
    "        self.visited = set()\n",
    "        init_string = self.to_string(board)\n",
    "        self.visited.add(init_string)\n",
    "        step = 0\n",
    "        queue = [board]\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                head = queue.pop(0)\n",
    "                if self.to_string(head) == self.target:\n",
    "                    return step\n",
    "\n",
    "                i, j = self.find_zero(head)\n",
    "                # 上\n",
    "                if i > 0:\n",
    "                    next = self.swap(i, j, i-1, j, head)\n",
    "                    next_string = self.to_string(next)\n",
    "                    if next_string not in self.visited:\n",
    "                        self.visited.add(next_string)\n",
    "                        queue.append(next)\n",
    "                # 下\n",
    "                if i < len(head) -1:\n",
    "                    next = self.swap(i, j, i+1, j, head)\n",
    "                    next_string = self.to_string(next)\n",
    "                    if next_string not in self.visited:\n",
    "                        self.visited.add(next_string)\n",
    "                        queue.append(next)\n",
    "                # 左\n",
    "                if j > 0:\n",
    "                    next = self.swap(i, j, i, j-1, head)\n",
    "                    next_string = self.to_string(next)\n",
    "                    if next_string not in self.visited:\n",
    "                        self.visited.add(next_string)\n",
    "                        queue.append(next)\n",
    "                # 右\n",
    "                if j < len(head[0])-1:\n",
    "                    next = self.swap(i, j, i, j+1, head)\n",
    "                    next_string = self.to_string(next)\n",
    "                    if next_string not in self.visited:\n",
    "                        self.visited.add(next_string)\n",
    "                        queue.append(next)\n",
    "            step += 1\n",
    "                \n",
    "        return -1\n",
    "    \n",
    "    def swap(self, ori_i, ori_j, new_i, new_j, board):\n",
    "        cur = copy.deepcopy(board)\n",
    "        temp = cur[ori_i][ori_j]\n",
    "        cur[ori_i][ori_j] = cur[new_i][new_j]\n",
    "        cur[new_i][new_j] = temp\n",
    "        return cur\n",
    "\n",
    "\n",
    "    def to_string(self, board):\n",
    "        tmp = [[str(item) for item in group] for group in board]\n",
    "        return \"\".join(tmp[0]) + \"\".join(tmp[1])\n",
    "\n",
    "    def find_zero(self, board):\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == 0:\n",
    "                    return i, j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def slidingPuzzle(self, board: List[List[int]]) -> int:\n",
    "        st = []\n",
    "        NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]\n",
    "\n",
    "        index = 0\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == 0:\n",
    "                    index = 3*i + j \n",
    "                st.append(board[i][j])\n",
    "        \n",
    "        def swap(lis,index1,index2):\n",
    "            l = lis.copy()\n",
    "            l[index1],l[index2] = l[index2],l[index1]\n",
    "            return l \n",
    "        st = [str(i) for i in st]\n",
    "        end = \"123450\"\n",
    "        q = deque()\n",
    "        q.append((st,index))\n",
    "        visited = set()\n",
    "        visited.add(''.join(st))\n",
    "        step = -1 \n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                cur,index = q.popleft()\n",
    "                if ''.join(cur) == end:\n",
    "                    return step \n",
    "                for nxtindex in NEIGHBORS[index]:\n",
    "                    a = swap(cur,index,nxtindex)\n",
    "                    s = str(a)\n",
    "                    if s not in visited:\n",
    "                        visited.add(s)\n",
    "                        q.append((a,nxtindex))\n",
    "        return -1\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
